36
class Solution {
    public boolean isValidSudoku(char[][] board) {
        int row = 9;
        int len = 9;
        int[] arr = new int[9];
        for (int i = 0; i  row; i++) {
            for (int j = 0; j  len; j++) {
                if (board[i][j] == '.') {
                    continue;
                }
                arr[board[i][j]-'1']++;
                if (arr[board[i][j]-'1'] == 2) {
                    return false;
                }
            }
            arr = new int[9];
        }

        for (int i = 0; i  len; i++) {
            for (int j = 0; j  row; j++) {
                if (board[j][i] == '.') {
                    continue;
                }
                arr[board[j][i]-'1']++;
                if (arr[board[j][i]-'1'] == 2) {
                    return false;
                }
            }
            arr = new int[9];
        }

        for (int i = 0; i  3; i++) {
            for (int j = 0; j  3; j++) {
                for (int k = 3i; k  3i+3; k++) {
                    for (int m = 3j; m  3j+3; m++) {
                        if (board[k][m] == '.') {
                            continue;
                        }
                        arr[board[k][m]-'1']++;
                        if (arr[board[k][m]-'1'] == 2) {
                            return false;
                        }
                    }
                }
                arr = new int[9];
            }
        }
        return true;
    }
}
给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

class Solution {
    public int longestPalindromeSubseq(String s) {
        char[] str = s.toCharArray();
        return maxString(str, 0, str.length-1);
    }

    public static int maxString(char[] str, int l, int r) {
        int[][] arr = new int[str.length][str.length];
        //因为不存在l < r的情况所以下三角的空间不用
        for (int i = 0; i < str.length; i++) {
            if (i == 0){//填第一条对角线
                int j = 0;
                while(j < str.length) {
                    arr[j][j] = 1;
                    j++;
                }
            }else if (i == 1) {//填第二条斜线
                int j = 1;
                while(j < str.length) {
                    arr[j - 1][j] = (str[j - 1] == str[j]) ? 2 : 1;
                    j++;
                }
            }else {
                int j = i;
                int k = 0;
                while(j < str.length){
                    int a1 = arr[k + 1][j - 1];
                    int a2 = arr[k][j - 1];
                    int a3 = arr[k + 1][j];
                    int a4 = str[k] == str[j] ? 2 + arr[k + 1][j - 1] : 0;
                    arr[k][j] = Math.max(Math.max(a1, a2), Math.max(a3, a4));
                    j++;
                    k++;
                }
            }

        }
        return arr[0][str.length-1];
    }
}